/**
 * Copyright (C) 2013 Daniel Gee.
 * See LICENSE.txt for more details.
 */
package com.rl.dungeon.pathing;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

import com.rl.dungeon.Location;

/**
 * Performs A* Pathfinding.
 * 
 * @author Daniel Gee
 */
public class AStar
{
	/**
	 * Computes a path from the <tt>start</tt> to the <tt>end</tt>, according to the <tt>map</tt>
	 * given. If the <tt>start</tt> or the <tt>end</tt> walkable within the map, then <tt>null</tt>
	 * is returned. If a path does not exist, then <tt>null</tt> is returned.
	 * 
	 * @param start
	 *            the starting location of the path.
	 * @param end
	 *            the ending point of the path.
	 * @param map
	 *            the movement costs to move through this space.
	 * @return the complete path, or <tt>null</tt> if no path exists.
	 */
	public static List<Location> computePath(Location start, Location end, MoveCostMap map)
	{
		// If the start or end aren't in the MoveCostMap given we can't make a path.
		if (!(map.isWalkable(start) && map.isWalkable(end)))
		{
			return null;
		}

		if (start.equals(end))
		{
			List<Location> retVal = new ArrayList<>();
			retVal.add(start);
			return retVal;
		}

		// our data sets.
		/**
		 * the queue of locations, sorted by fCost
		 */
		final Queue<CostedLocation> openQueue = new PriorityQueue<>();
		/**
		 * The set of locations we've closed on.
		 */
		final Set<Location> closedSet = new HashSet<>();
		/**
		 * A mapping that maps a Location to its parent.
		 */
		final Map<Location, Location> parentMap = new HashMap<>();
		/**
		 * A mapping that maps a Location to its gCost (go-to cost)
		 */
		final Map<Location, Integer> gCost = new HashMap<>();
		/**
		 * A mapping that maps a Location to its hCost (heuristic cost)
		 */
		final Map<Location, Integer> hCost = new HashMap<>();

		// Initialize the datasets.
		gCost.put(start, 0);
		hCost.put(start, start.manhattanDistance(end));
		openQueue.add(new CostedLocation(start, gCost.get(start) + hCost.get(start)));

		// We keep doing this loop as long as we have open locations to go to.
		while (!openQueue.isEmpty())
		{
			// Pull the lowest fCost Location out and start working around it.
			Location active = openQueue.poll().location;

			for (Location loc : map.getLocationsAccessableFrom(active))
			{
				if (loc.equals(end))
				{
					parentMap.put(loc, active);
					return AStar.pathBuilder(parentMap, end);
				}
				if (closedSet.contains(loc))
				{
					continue;
				}
				/**
				 * If an adjacent square is already on the open list, check to see if this path to
				 * that square is a better one. In other words, check to see if the G score for that
				 * square is lower if we use the current square to get there. If not, don't do
				 * anything. On the other hand, if the G cost of the new path is lower, change the
				 * parent of the adjacent square to the selected square (in the diagram above,
				 * change the direction of the pointer to point at the selected square). Finally,
				 * recalculate both the F and G scores of that square.
				 */
				boolean alreadySeenThisLocation = false;
				for (CostedLocation cl : openQueue)
				{
					if (cl.location.equals(loc))
					{
						alreadySeenThisLocation = true;
						if (gCost.get(cl.location) < gCost.get(active) + map.getMoveCostAt(loc))
						{
							// do nothing, stored gCost is less than what the new gCost would be.
						}
						else
						{
							parentMap.put(loc, active);
							gCost.put(loc, gCost.get(active) + map.getMoveCostAt(loc));
							openQueue.remove(cl);
							openQueue.add(new CostedLocation(loc, gCost.get(loc) + hCost.get(loc)));
							break;
						}
					}
				}
				if (!alreadySeenThisLocation)
				{
					parentMap.put(loc, active);
					gCost.put(loc, gCost.get(active) + map.getMoveCostAt(loc));
					hCost.put(loc, loc.rogueDistance(end));
					openQueue.add(new CostedLocation(loc, gCost.get(loc) + hCost.get(loc)));
				}
			}
			closedSet.add(active);
		}

		return null;
	}

	/**
	 * Finds the closest location that satisfies the <tt>condition</tt> specified. Returns
	 * <tt>null</tt> if the starting location isn't within the map given, or if the search is
	 * exhausted without finding a satisfactory location.
	 * 
	 * @param start
	 *            the starting location of the path.
	 * @param condition
	 *            the conditions that must be correct for the end point.
	 * @param map
	 *            the movement costs to move through this space.
	 * 
	 * @return a path to the shortest acceptable location.
	 */
	public static List<Location> findNearest(Location start, LocationPredicate condition,
			MoveCostMap map)
	{
		// If the start or end aren't in the MoveCostMap given we can't make a path.
		if (!map.isWalkable(start))
		{
			return null;
		}

		if (condition.isSatisfactoryAt(start))
		{
			List<Location> retVal = new ArrayList<>();
			retVal.add(start);
			return retVal;
		}

		/**
		 * List of Locations we haven't yet explored.
		 */
		final List<Location> openList = new ArrayList<>();
		/**
		 * The set of locations we've already explored.
		 */
		final Set<Location> closedSet = new HashSet<>();
		/**
		 * A mapping that maps a Location to its parent.
		 */
		final Map<Location, Location> parentMap = new HashMap<>();
		/**
		 * A mapping that maps a Location to its gCost (go-to cost)
		 */
		final Map<Location, Integer> gCost = new HashMap<>();

		// Initialize the datasets.
		gCost.put(start, 0);
		openList.add(start);

		// We keep doing this loop as long as we have open locations to go to.
		while (!openList.isEmpty())
		{
			// Pull the lowest fCost Location out and start working around it.
			Location active = openList.remove(0);

			for (Location loc : map.getLocationsAccessableFrom(active))
			{
				if (condition.isSatisfactoryAt(loc))
				{
					parentMap.put(loc, active);
					return AStar.pathBuilder(parentMap, loc);
				}
				if (closedSet.contains(loc))
				{
					continue;
				}
				boolean alreadySeenThisLocation = false;
				for (Location opl : openList)
				{
					if (opl.equals(loc))
					{
						alreadySeenThisLocation = true;
						if (gCost.get(opl) < gCost.get(active) + map.getMoveCostAt(loc))
						{
							// do nothing, stored gCost is less than what the new gCost would be.
						}
						else
						{
							parentMap.put(loc, active);
							gCost.put(loc, gCost.get(active) + map.getMoveCostAt(loc));
							break;
						}
					}
				}
				if (!alreadySeenThisLocation)
				{
					parentMap.put(loc, active);
					gCost.put(loc, gCost.get(active) + map.getMoveCostAt(loc));
					openList.add(loc);
				}
			}
			closedSet.add(active);
		}

		return null;
	}

	/**
	 * @param parentMap
	 * @param end
	 * @return
	 */
	private static List<Location> pathBuilder(Map<Location, Location> parentMap, Location end)
	{
		List<Location> retVal = new ArrayList<Location>();

		Location active = end;
		while (active != null)
		{
			retVal.add(active);
			active = parentMap.get(active);
		}

		Collections.reverse(retVal);
		return retVal;
	}
}
